package solution.design;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2022-05-23 11:38
 * 前缀树问题：
 *
 */
public class Trie_Solution {
    /** ========================================================================
     * 648. 单词替换
     * 在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。
     * 例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
     * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
     * 你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
     * 你需要输出替换之后的句子。
     * 思路：
     * 1、用HashSet来存储词根，然后每个单词的前缀去判断是否在词根中存在
     * 2、前缀树，把所有前缀都放入前缀树中，在树上查找每个单词的最短词根，该操作可在线性时间内完成。
    * */
    public String replaceWords1(List<String> dictionary, String sentence) {
        Set<String> rootset=new HashSet<>();
        for (String root: dictionary) {
            rootset.add(root);
        }
        StringBuffer res=new StringBuffer();
        for(String word:sentence.split(" ")){
            String prefix="";
            for (int i = 0; i < word.length(); i++) {
                prefix=word.substring(0,i+1);
                if (rootset.contains(prefix)) break;
            }
            if (res.length()>0) res.append(" ");
            res.append(prefix);
        }
        return res.toString();
    }
    class TrieNode{
        TrieNode[] children;
        String word;
        TrieNode(){
            children=new TrieNode[26];
        }
    }
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode trie=new TrieNode();
        //将词根插入的trie树中
        for (String root:dictionary) {
            TrieNode cur=trie;
            for (char c:root.toCharArray()) {
                if (cur.children[c-'a']==null){
                    cur.children[c-'a']=new TrieNode();
                }
                cur=cur.children[c-'a'];
            }
            cur.word=root;
        }
        StringBuffer res=new StringBuffer();
        for (String word:sentence.split(" ")) {
            if (res.length()>0){
                res.append(" ");
            }
            TrieNode cur=trie;
            for (char c:word.toCharArray()) {
                if (cur.children[c-'a']==null||cur.word!=null) break;
                cur=cur.children[c-'a'];
            }
            res.append(cur.word!=null?cur.word:word);
        }
        return res.toString();
    }
}
